/**
 * @a https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
 */

struct ListNode {
   int val;
   ListNode *next;
   ListNode() : val(0), next(nullptr) {}
   ListNode(int x) : val(x), next(nullptr) {}
   ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast, *slow,*dummy;
        dummy = new ListNode(-1, head);
        slow = fast = dummy;
        for(int i = 0; i <= n; ++i)// fast 走 n+1 步
        {
            fast = fast->next;
        }
        while(fast != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* rm = slow->next;

        slow->next = rm->next;
        delete rm;
        rm = nullptr;
        ListNode* newHead = dummy->next;
        delete dummy;
        dummy = nullptr;
        return newHead;
    }
};